This invention relates to a method and apparatus for reducing three-dimensional shape data forming a polygon model.
A huge number of measurement data are obtained by, for example, a three-dimensional shape measuring apparatus having quite a high space resolution if an image quality is high. Accordingly, if the data have a higher image quality than necessary, it disadvantageously results in a large burden on a storage device during succeeding processing and a considerable reduction in processing speed. Thus, it is necessary to ease this problem as much as possible by reducing the number of measurement data. However, in such a case, if a difference between a polygon model (hereinafter, referred to as approximated polygon model) formed by the measurement data after the data reduction and a polygon model formed by the actually measured three-dimensional shape data (hereinafter, referred to as original polygon model) is excessively large, the measurement data after the data reduction cannot be effectively utilized. Therefore, it is necessary to control error between the approximated polygon model and the original polygon model in the data reduction.
Particularly in the case of three-dimensional shape data obtained by a three-dimensional shape measuring apparatus, actually measured three-dimensional shape data are converted into an approximate value by the data reduction. Thus, error between the approximated polygon model and the original polygon model is preferably controlled using the actually measured three-dimensional shape data as a reference.
On the other hand, various methods have been proposed to reduce the number of three-dimensional data forming a triangular polygon model by approximating a model within a desired permissible error range.
For example, in “Hierarchical Approximation of Three-Dimensional Polygon Models” (by Horikawa and Totsuka, pp. 3-7 of Proceedings of the 5th Sony Research Forum, 1995) is disclosed a method for reducing the number of three-dimensional shape data by estimating contributions of respective edges forming a triangular polygon model in the form of an estimation function expressing a volume which changes in the case that edges are deleted, and deleting edges, for example, in the case that they are parallel to surrounding surfaces, surfaces are small and/or edges are short.
Further, in “Simplification Envelopes” (by Cohen Jonathan, Amitabh Varshney, Dinesh Manocha, Greg Turk, Hans Weber, Pankai Agarwal, Frederick Brooks and William Wright, pp. 119-128 of Proceedings of SIGGRAPH 96 in Computer Graphics Proceedings, Annual Conference Series, 1996, ACM SIGGRAPH) is disclosed a method for generating models obtained by reducing an original polygon model by an error ε and enlarging it by the error E and reducing the number of data of the original polygon model such that an approximate polygon model lies between the enlarged and reduced models.
Further, in “Surface Simplification Using Quadric Error Metrics” (by Michael Garland and Paul S. Heckbert, Carnegie Mellon University, Proceedings of SIGGRAPH 97, 1997) is disclosed a method for reducing the number of three-dimensional shape data forming a triangular polygon model by converging two or more vertices (three-dimensional shape data) forming an edge or surface of the triangular polygon model to one vertex. In this method, a distance between the converged vertex due to edge shrinking or surface shrinking and the respective planes forming the original triangular polygon model influenced by the edge shrinking or surface shrinking is controlled as an error in the data reduction. The number of data is reduced within a specified permissible error range by performing such an edge shrinking or surface shrinking that this error lies within a specified permissible range.
In this method, specifically, when the edge shrinking is applied for one edge, the error estimation is executed for the other edges or surfaces of the polygon model that are to be influenced by the edge shrinking because the shrinking of the one edge changes edges and surfaces surrounding the one edge. After the error calculation is completed, the shrinking of the one edge is determined. This processing is repeated to reduce the number of the three-dimensional shape data within a predetermined permissible range.
Since the data reducing method disclosed in “Hierarchical Approximation of Three-Dimensional Polygon Models” only deletes edges based on evaluation values thereof, an error in the approximation of a model by the edge deletion cannot be estimated although the three-dimensional data of characteristic portions of a polygon model remain. Thus, this method is effective in the case of reducing the number of data of a polygon model for merely displaying a three-dimensional image such as virtual reality and games in computer graphics. However, this method cannot be effective in the case that the error between the original measurement data and the data of the approximated model after the data reduction needs to be controlled.
On the other hand, the data reducing method disclosed in “Simplification Envelopes” can strictly control such error. However, it is necessary to generate polygon models by enlarging and reducing the original polygon model by an error ε and save the data of these polygon models during the data reduction. Thus, the number of data relating to the processing becomes huge, causing the problem of large burden on the memory capacity and calculations for the data reduction.
Further, the method disclosed in “Surface Simplification Using Quadric Error Metrics” controls the distances from the vertices of the polygon model after the approximation from the surfaces forming the original polygon model as errors. Thus, this method is not necessarily a suitable method in the case that data reduction is desired to be performed by controlling errors of the polygon models after the approximation from the vertices forming the original polygon model like the measurement data of the three-dimensional shape measuring apparatus.
Further, in the case of measurement data obtained by measuring rough surfaces or cut surfaces of a measurement object by means of a three-dimensional shape measuring apparatus, e.g., in the case that the orientation of surfaces locally suddenly change in a zigzag manner in a polygon model, errors for these zigzag surfaces are estimated. Therefore, errors are estimated as large values as the data reduction progresses, thereby presenting the problem of insufficient data reduction.
Furthermore, each time the edge or surface shrinking is performed, it is necessary to estimate errors with respect to the edges or surfaces of the shrunk polygon model that are to be influenced by the edge or surface shrinking. This will increase the number of calculations, consequently causing the problem of hindering the data reduction.